package com.ma.dp.stock;

/**
 * @ClassName SolutionAll
 * @Author: mayongqiang
 * @DATE 2022/4/25 15:00
 * @Description: 股票问题的整合  leetcode  121 122 123  188 309 714
 */
public class SolutionAll {
    public static void main(String[] args) {

    }

    /*
      输入股票价格数组 prices，你最多进行 max_k 次交易，每次交易需要额外消耗 fee 的手续费，
        而且每次交易之后需要经过 coolDown 天的冷冻期才能进行下一次交易，
            请你计算并返回可以获得的最大利润。


     1、dp数组的定义
        这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态(我们不妨用 1 表示持有，0 表示没有持有）。
            然后我们用一个三维数组就可以装下这几种状态的全部组合：
            dp[i][k][0 or 1]
            0 <= i <= n - 1, 1 <= k <= K
            n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
            此问题共 n × K × 2 种状态，全部穷举就能搞定。

            for 0 <= i < n:
                for 1 <= k <= K:
                    for s in {0, 1}:
                        dp[i][k][s] = max(buy, sell, rest)

            dp[3][2][1] 的含义：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。
            dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易
      2、状态转移
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
                          max( 今天选择 rest,        今天选择 sell       )
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
                          max( 今天选择 rest,         今天选择 buy         )
                          这里着重提醒一下，时刻牢记「状态」的定义，状态 k 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。
                          如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 k，那么昨天的最大交易次数上限必须是 k - 1。
      dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k][1]+price[i])
      dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-price[i])

    */
    private static int maxProfit_all_in_one(int max_k, int[] prices, int coolDown, int fee) {
        int n = prices.length;
        if (n <= 0) {
            return 0;
        }
        if (max_k > n / 2) {
            // 交易次数 k 没有限制的情况
            return maxProfit_k_inf(prices, coolDown, fee);
        }

        int[][][] dp = new int[n][max_k + 1][2];
        // k = 0 时的 base case
        for (int i = 0; i < n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < n; i++)
            for (int k = max_k; k >= 1; k--) {
                if (i - 1 == -1) {
                    // base case 1
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i] - fee;
                    continue;
                }

                // 包含 coolDown 的 base case
                if (i - coolDown - 1 < 0) {
                    // base case 2
                    dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                    dp[i][k][1] = Math.max(dp[i - 1][k][1], -prices[i] - fee);
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                // 同时考虑 coolDown 和 fee
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - coolDown - 1][k - 1][0] - prices[i] - fee);
            }
        return dp[n - 1][max_k][0];

    }

    // k 无限制，包含手续费和冷冻期
    private static int maxProfit_k_inf(int[] prices, int coolDown, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            if (i - 1 == -1) {
                // base case 1
                dp[i][0] = 0;
                dp[i][1] = -prices[i] - fee;
                continue;
            }

            // 包含 coolDown 的 base case
            if (i - coolDown - 1 < 0) {
                // base case 2
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                // 别忘了减 fee
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i] - fee);
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 同时考虑 coolDown 和 fee
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - coolDown - 1][0] - prices[i] - fee);
        }
        return dp[n - 1][0];

    }
}